package com.example.demo.algorithm.graph;

import com.example.demo.algorithm.linear.Queue;

/**
 * @Author: xiatian
 * @CreateTime: 2022/2/5 12:55 下午
 * @Description:广度优先搜索
 */
public class BreadthFirstSearch {
    //索引记录顶点，值标识该节点是否已经被搜索
    private boolean[] marked;
    //索引记录顶点，值标识该节点是否已经加入到待搜索队列中
    private boolean[] joinMarked;
    //记录有多少个顶点与s顶点相通
    private int count;
    //用来存储待搜索领接表的顶点
    private Queue<Integer> waitSearch;

    /**
     * 构造广度优先搜索对象，使用广度优先搜索g图中s顶点的所有相通的顶点
     *
     * @param g
     * @param s
     */
    public BreadthFirstSearch(Graph g, int s) {
        this.marked = new boolean[g.V()];
        this.count = 0;
        this.waitSearch = new Queue<Integer>();
        this.joinMarked = new boolean[g.V()];
        bfs(g, s);
    }

    /**
     * 使用广度优先搜索找出g图中v顶点所有相通的点
     *
     * @param g
     * @param v
     */
    private void bfs(Graph g, int v) {
        //让顶点v进入队列，待搜索
        waitSearch.enqueue(v);
        joinMarked[v] = true;

        //通过循环，如果队列不为空，则从队列中弹出一个带搜索的顶点进行搜索
        while (!waitSearch.isEmpty()) {
            //弹出一个待搜索的顶点
            Integer wait = waitSearch.dequeue();
            marked[wait] = true;
            //让相通的顶点+1
            count++;
            //遍历wait顶点的领接表
            for (Integer w : g.adj(wait)) {
                if (!joinMarked[w]) {
                    waitSearch.enqueue(w);
                    joinMarked[w] = true;
                }
            }
        }

    }

    //判断顶点w与s顶点是否相通
    public boolean marked(int w) {
        return marked[w];
    }

    //获取与顶点s相通的所有顶点的总数
    public int count() {
        return count;
    }

}
